1. Field of the Invention
The present invention relates generally to memory systems in a personal computer system. More particularly, the present invention relates to the manner and techniques by which memory is accessed by components in a computer system. Still more particularly, the invention relates to an improved technique for arbitrating among multiple pending memory requests.
2. Background of the Invention
Modem computer system generally include a plurality of devices interconnected through a system of buses which are linked by way of one or more hubs, or bridge logic units. For example, a conventional computer system typically contains a central processing unit (xe2x80x9cCPUxe2x80x9d) or processor coupled through bridge logic to main memory. A CPU bus usually couples the CPU to the bridge logic, and a memory bus connects the bridge logic to the main memory. The bridge logic typically incorporates a memory controller which receives memory access requests and generates the standard control signals necessary to access the main memory. The bridge logic may also include an interface to a high bandwidth local expansion bus, such as the Peripheral Component Interconnect (xe2x80x9cPCIxe2x80x9d) bus. Examples of devices which link to the local expansion bus include network interface cards, video accelerators, audio cards, SCSI adapters, and telephony cards, to name a few. An example of such a bridge logic is described in U.S. Pat. No. 5,634,073, assigned to Compaq Computer Corporation.
Bridge logic may also support an older-style expansion bus through an additional bus interface to provide compatibility with earlier-version expansion bus adapters. Examples of such expansion buses include the Industry Standard Architectures (ISA) bus, the Extended Industry Standard Architecture (xe2x80x9cEISAxe2x80x9d) bus, and the Microchannel Architecture (MCA) bus. Various devices may be coupled to this second expansion bus including a fax/modem, sound card, keyboard, and other peripherals. The bridge logic can link or interface more than simply the CPU bus, a peripheral bus such as a PCI bus, and the memory bus. In graphics-intensive applications, bridge logic may support a separate peripheral bus optimized for graphics related data transfers. A popular example of such a bus is the Advanced Graphic Port (xe2x80x9cAGPxe2x80x9d) bus.
Because many of the devices interconnected through this series of buses function independently of each other, they often attempt to access common resources concurrently. For example, a device coupled to the AGP bus may need to extract data from main memory to drive a video display at the same time the CPU is requesting instructions stored in main memory that allow the video program to run. Both actions require memory access, and the memory controller must choose which device (the CPU or the AGP device in this example) to service first. Such conflicts necessitate arbitration, in which priority ratings are assigned to rank memory requests and allow the memory controller to service memory requests by order of importance.
Since computer systems have traditionally been developed for business applications including word processing and spreadsheets, among others, the arbitration schemes within such systems have generally been geared to guarantee the highest memory access priority to a single device (such as the CPU), with lower priority rankings assigned to the remaining devices in the computer. Using such a fixed priority scheme, a memory controller, if faced with multiple pending memory access requests, simply grants memory access to the device with the highest priority, traditionally the CPU. A fixed-priority arbitration scheme is generally well-suited to the more traditional computer application programs, which tend to involve relatively minor levels of user input, device interaction, and graphics output.
Recently, however, computer systems have been increasingly employed in processing real-time data, including multimedia applications such as video and audio, telephony, and speech recognition. The performance of these applications suffers if the computer cannot process the real-time data within a minimum time period. When the CPU or other highly prioritized device issues numerous memory access requests, the memory controller is prevented from granting access to lower-ranking devices, even if those devices are processing real-time data. Until the high-priority devices stop issuing memory access requests, the low-priority real-time applications are forced to stall and wait for access to memory. Accordingly, fixed-priority memory arbitration techniques may be unacceptable for real-time applications, such as video, where unintended pauses in the on-screen action can ruin the effect of a moving picture, or in speech recognition, where failure to capture portions of the speech data can prevent the computer from recognizing what a speaker said. Hence, fixed memory arbitration schemes often are inadequate to support the memory demands of emerging computer applications.
The Least-Recently-Used (LRU) algorithm, in which a memory arbiter grants the request which has least recently been granted, is one alternative to fixed arbitration schemes since the priority structure of an LRU scheme may change in response to the memory request sequence. However, this type of responsive priority change essentially equalizes, or fixes, the priority of all devices in the computer system, since the arbitration scheme does not take into account the urgency associated with memory transactions from certain devices. Further, the devices which use memory infrequently actually tend to experience shorter waits for memory access, since these devices are less likely to have recently accessed memory than are devices which access memory more frequently. As a consequence, real-time applications and devices, which need frequent and quick access to memory, may consistently lose memory arbitration to other devices under an LRU scheme. Hence, an LRU scheme, while more equitable that a fixed scheme, lacks the flexibility to allow the computer system designer to directly set the memory request priorities.
For the foregoing reasons, it would be advantageous to design a computer system that includes a bus bridge architecture that permits all devices in a computer system fair access to memory, without incurring the drawbacks of current arbitration methods. A memory controller with an equitable, yet configurable, arbitration scheme could dramatically improve the quality of service associated with memory accesses in modern computer applications. Despite the apparent advantages that such a system would provide, to date no such system has been developed that provides these features.
The deficiencies of the prior art described above are solved in large part by a computer system configured in accordance with the present invention. The computer system of the present invention preferably includes a processor, a memory device, two expansion buses, and a bridge logic unit coupling together the CPU, the memory device and the expansion buses. The bridge logic unit incorporates a memory controller implementing an adaptive (or xe2x80x9cdynamicxe2x80x9d) memory-request arbitration scheme. The CPU couples to the bridge logic unit via a CPU bus and the memory device couples to the bridge logic unit via a memory bus. In accordance with an embodiment of the invention, one expansion bus is implemented as a peripheral component interconnect (xe2x80x9cPCIxe2x80x9d) bus and the other expansion bus is an accelerated graphics port (xe2x80x9cAGPxe2x80x9d) bus. The bridge logic unit generally routes bus cycle requests from one of the four buses (CPU, memory, PCI, AGP) to another of the four buses while concurrently routing bus cycle requests between other pairs of buses. In addition to the ability to concurrently route bus cycle requests, the bridge logic unit also has the circuitry necessary to implement an adaptive memory access arbitration scheme.
The bridge logic unit preferably includes a CPU interface, a memory controller, an AGP bus interface, and a PCI bus interface. Each pair of interfaces (including the memory controller) preferably are cupled by at least one queue. The queues temporarily store read data and/or write requests, with the write requests comprising write addresses and write data. Accordingly, the bridge logic unit includes a plurality of write queues for storing write requests from one interface to another and a plurality of read queues for storing read data between interfaces. By way of example, the CPU, PCI, and AGP interfaces couple to the memory controller via write queues in which each interface can concurrently store (or xe2x80x9cpostxe2x80x9d) memory write requests. The queues preferably provide the capacity to store two or more write requests (for the write queues) or read data streams (for the read queues).
Because each interface may communicate concurrently with all other interfaces (including the memory controller) via the read and write queues, the possibility exists that a first interface cannot access main memory because main memory is processing read or write requests from a second interface. For example, a device coupled to the PCI bus may not be able to read from memory because the CPU is currently writing data to memory. In such a situation, the PCI device may become xe2x80x9cstarvedxe2x80x9d for memory access. To remedy such problems, the bridge logic unit contains a memory controller capable of mediating between memory requests. The memory controller implements an adaptive arbitration scheme that updates memory request priority rankings regularly, in order to favor the memory requests that have been refused service during previous memory cycles. In such an arbitration system, requests that are refused service receive progressively higher priority rankings. Requests initially having low priority thereby advance in priority until they are granted service. Such an arbitration system keeps the memory controller from ignoring some memory requests indefinitely and therefore prevents any device in the computer system from becoming starved for memory access.
Thus, the present invention comprises a combination of features and advantages which enable it to overcome various problems of prior devices. The various characteristics described above, as well as other features, will be readily apparent to those skilled in the art upon reading the following detailed description of the preferred embodiments of the invention and by referring to the accompanying drawings.